%======================================================================
%----------------------------------------------------------------------
%               XX                           X
%                                            X
%               XX    XXX   XXX   XXX   XXX  X  XXXX
%                X   X   X X   X X   X X   X X X
%                X   XXXXX XXXXX XXXXX X     X  XXX
%                X   X     X     X     X   X X     X
%               XXX   XXX   XXX   XXX   XXX  X XXXX
%----------------------------------------------------------------------
%               SPECIFICATION FOR COMMON IEEE STYLES
%----------------------------------------------------------------------
%               Gregory L. Plett, Istv\'{a}n Koll\'{a}r.
%======================================================================
\documentclass[%
    %draft,
    %submission,
    %compressed,
    a4paper,
    %12pt,
    10pt,
    final,
    %technote,
    %internal,
    %submitted,
    %inpress,
    %reprint,
    %titlepage,
    notitlepage,
    %anonymous,
    narroweqnarray,
    inline,
    oneside,
    %invited,
    %conference
    article
    ]{ieee}

%\documentclass[a4paper,12pt]{article}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{epstopdf}

\newcommand{\latexiie}{\LaTeX2{\Large$_\varepsilon$}}

%\usepackage{ieeetsp}    % if you want the "trans. sig. pro." style
%\usepackage{ieeetc}    % if you want the "trans. comp." style
%\usepackage{ieeeimtc}    % if you want the IMTC conference style

% Use the `endfloat' package to move figures and tables to the end
% of the paper. Useful for `submission' mode.
%\usepackage {endfloat}

% Use the `times' package to use Helvetica and Times-Roman fonts
% instead of the standard Computer Modern fonts. Useful for the
% IEEE Computer Society transactions.
%\usepackage{times}
% (Note: If you have the commercial package `mathtime,' (from
% y&y (http://www.yandy.com), it is much better, but the `times'
% package works too). So, if you have it...
%\usepackage {mathtime}

% for any plug-in code... insert it here. For example, the CDC style...
%\usepackage{ieeecdc}

\begin{document}

%----------------------------------------------------------------------
% Title Information, Abstract and Keywords
%----------------------------------------------------------------------
\title[]{
  Trabajo Práctico Especial 1: Algoritmos de B\'usqueda}

% format author this way for journal articles.
% MAKE SURE THERE ARE NO SPACES BEFORE A \member OR \authorinfo
% COMMAND (this also means `don't break the line before these
% commands).
%\author[PLETT AND KOLL\'{A}R]{Gregory L. Plett\member{Student
%       Member},\authorinfo{G.\,L.\,Plett is with the Department of Electrical
%       Engineering, Stanford University, Stanford, CA 94305--9510.
%       Phone: $+$1\,650\,723--4769, e-mail: glp@simoon.stanford.edu}%
%\and{}and Istv\'{a}n Koll\'{a}r\member{Fellow}\authorinfo{I.\
%       Koll\'{a}r is with the Department of Measurement and Information
%       Systems, Technical University of Budapest, 1521 Budapest, Hungary.
%       Phone: $+$\,36\,1\,463--1774, fax: +\,36\,1\,463--4112,
%       e-mail: kollar@mmt.bme.hu}
%}
\author{
     Alan Idesis,
\and Mar\'ia Eugenia Cura,
\and Tom\'as Alvarez
}

% format author this way for conference proceedings
%\author[PLETT AND KOLL\'{A}R]{%
        %Gregory L. Plett\member{Student Member},\authorinfo{%
        %Department of Electrical Engineering,\\
        %Stanford University, Stanford, CA 94305-9510.\\
        %Phone: $+$1\,650\,723-4769, email: glp@simoon.stanford.edu}%
%\and{}and%
%\and{}Istv\'{a}n Koll\'{a}r\member{Fellow}\authorinfo{%
        %Department of Measurement and Instrument Engineering,\\
        %Technical University of Budapest, 1521 Budapest, Hungary.\\
        %Phone: $+$\,36\,1\,463-1774, fax: +\,36\,1\,463-4112,
        %email: kollar@mmt.bme.hu}
%}

%\journal{IEEE Trans.\ on Instrum.\ Meas.}
%\titletext{, VOL.\ 46, NO.\ 6, DECEMBER\ 1997}
%\ieeecopyright{0018--9456/97\$10.00 \copyright\ 1997 IEEE}
%\lognumber{xxxxxxx}
%\pubitemident{S 0018--9456(97)09426--6}
%\loginfo{Manuscript received September 27, 1997.}
%\firstpage{1217}

%\confplacedate{Ottawa, Canada, May 19--21, 1997}

\maketitle

%\begin{keywords}
%Style file, \latexiie, Microsoft Word, IEEE Publications, Instrumentation
%and Measurement Technology Conference, IMTC.
%\end{keywords}

%----------------------------------------------------------------------
% SECTION I: Introduction
%----------------------------------------------------------------------
\section{Introducci\'on}

\PARstart El objetivo de este trabajo pr\'actico es utilizar distintos algoritmos de b\'usqueda 
informados para resolver un determinado problema. Se analizaran y compararan 
los resultados obtenidos de los algoritmos informados de este trabajo con los resultados de los no informados realizados en el 
trabajo preeliminar anterior.

El problema a resolver es el juego Fill Zone (v\'ease[1]). Se parte de un estado inicial con un tablero cuyas celdas est\'an pintadas con un color de entre seis posibles, y el objetivo es propagar el color de la celda en la esquina superior izquierda
al resto del tablero, hasta que todo el tablero posea el mismo color. Para ello, se elije en cada turno
el nuevo color de la esquina superior izquierda, el cual se propaga a trav\'es de las celdas adyacentes.

Los algoritmos de b\'usqueda informados a utilizar en este trabajo son Greedy Search y A*, ademas de DFS, BFS, y Profundizaci\'on
iterativa que estaban implementados para el trabajo anterior. En la secci\'on II se trata el desarrollo del trabajo. Se explican las consideraciones que se tuvieron en cuenta para realizarlo. En la secci\'on III se muestran los resultados obtenidos con
los distintos m\'etodos de b\'usqueda y se sacan las correspondientes conclusiones sobre dichos resultados.
En la secci\'on IV se presentan algunos comentarios finales.



%----------------------------------------------------------------------
% SECTION II: The Document Life-Cycle
%----------------------------------------------------------------------

\section{Desarrollo}

En esta secci\'on se trata el desarrollo del problema. Para ello es importante analizar los estados, las reglas a utilizar,
la funci\'on de costo y las heur\'isticas propuestas.

\subsection{Representaci\'on de estados}

El estado de un nodo est\'a representado como el conjunto
de los estados de cada una de las celdas del tablero. En
el problema que se est\'a estudiando en este trabajo se
consideran tableros de distintos tama\~nos ($8x8$, $10x10$ y $14x14$).

Una celda se la representa como una 2-upla de la siguiente manera:
\[
  \left[C, V\right]
\]
donde
\begin{itemize}
 \item C: Representa el color de la celda. La misma puede ser cualquiera
 de los seis colores disponibles en el juego (blanco, amarillo, rosa, rojo,
azul, verde).
\item V: Indica si la celda fue visitada, utilizado para el algoritmo que
propaga el color elegido en cada turno.
\end{itemize}
Con \'esta representaci\'on se pueden distinguir todos los estados posibles que puede
tener el tablero.

\subsection{Reglas}
En este problema, las reglas representan los posibles
cambios de color. A partir de las mismas se efect\'uan los cambios
de estado dentro del tablero. Las reglas definidas para este problema son las siguientes:
\begin{enumerate}
 \item Propagar color blanco
 \item Propagar color amarillo
 \item Propagar color rosa
 \item Propagar color azul
 \item Propagar color rojo
 \item Propagar color verde
\end{enumerate}
Estas son las reglas determinadas para explotar los nodos e ir expandiendo el \'arbol de b\'usqueda del problema.

\subsection{Funci\'on de costo}
La m\'etrica utilizada para obtener el costo de la b\'usqueda es la cantidad de cambios de color a realizar. El
estado inicial del tablero tiene costo igual a cero. El estado que surge de realizar alg\'un cambio de color
a partir del estado inicial va a tener costo igual a uno. Acorde a esta m\'etrica, el costo que va a tener el estado
goal, va a ser equivalente a la cantidad de cambios de color que demande resolver el problema.
Es importante notar que el costo de un nodo coincide con el nivel de profundidad que dicho nodo posee dentro del
\'arbol de b\'usqueda. Denotaremos el costo desde un estado inicial a un nodo cualquiera $n$ como $g(n)$.

\subsection{Algoritmos Informados}
Se implementaron dos algoritmos de b\'usqueda informados. \textbf{Greedy Search} y \textbf{A*}. A continuaci\'on se exponen
detalles de notaci\'on utilizados para este informe:

\begin{itemize}
 \item \textbf{$f(n)$}: costo estimado de la soluci\'on m\'as barata que pasa por el nodo $n$
 \item \textbf{$h(n)$}: estimaci\'on del m\'inimo costo de la ruta que va del nodo $n$ a un nodo objetivo $n_g$
\end{itemize}


\subsection{Heur\'isticas}
Para la resoluci\'on de este trabajo se implementaron y probaron tres heur\'isticas y una combinaci\'on de dos de ellas. En la secci\'on
III pueden verse los resultados de su aplicaci\'on con los dos algoritmos de b\'usqueda informados que se utilizaron.


\subsection{Primera Heur\'istica $H_1$}
La primera heur\'istica consiste en ver cu\'al es la cantidad de colores diferentes que hay en el tablero menos uno. 
En el estado inicial la cantidad de colores es equivalente a 5 y en el estado final es 0. 
Por ejemplo, en la Figura \ref{fig2}, llamando $h_1(n)$ a la heur\'istica 1 aplicada al nodo $n$  el valor es $h_1(n) = 3$ 
mientras que en la Figura \ref{fig3} es  $h_1(n) = 2$.
Esta heur\'istica cumple que $h(n_{g}) = 0$ siendo $n_{g}$ un nodo \textit{goal} y es admisible ya que no sobreestima el valor real. 
El problema es que se vuelve \'util comenzar a aplicarla recien en los \'ultimos niveles del juego, 
cuando el tablero ya se encuentra casi todo del mismo color. 
Hasta ese momento, la heur\'istica devuelve siempre el mismo valor ya que en la mayor\'ia de los niveles del juego, 
la cantidad de colores va a ser 6. Por esta raz\'on, utilizar esta heur\'istica en un tablero superior a $8x8$ 
es casi lo mismo que utilizar un m\'etodo de b\'usqueda no informado hasta llegar a los niveles de profundidad
pr\'oximos al de la soluci\'on \'optima.

\subsection{Segunda Heur\'istica $H_2$}
La tercera heur\'istica que se implement\'o consiste en encontrar el camino m\'inimo
desde el cluster del color activo al cluster que se encuentra m\'as alejado. 
Para esto, inicialmente se construy\'o un grafo con pesos a partir de la matriz que representa al estado de un nodo. 
El peso entre las celdas adyacentes se defini\'o como $0$ si compart\'ian el mismo color o $1$ si ten\'ian uno distinto. 
La distancia del camino m\'inimo representa la cantidad m\'inima de movidas necesarias para alcanzar al cluster m\'as lejano
y convertirlo al color del cluster principal. El problema con esta heur\'istica es que es muy cara para calcular,
ya que por cada nodo se debe transformar su estado a un grafo y luego calcular el camino m\'inimo. 
Esta heur\'istica es admisible y encuentra el camino \'optimo pero al ser su procesamiento computacionalmente caro trae problemas de memoria y velocidad. En una posterior optimizaci\'on, se logr\'o realizar el c\'alculo del algoritmo de Dijkstra directamente sobre la matriz sin necesidad de convertirla a un grafo, reduciendo un poco el tiempo de procesamiento de la misma.

\subsection{Tercera Heur\'istica $H_3$}
La segunda heur\'istica consiste en determinar, dado un estado, cu\'al es el tama\~no del cluster\footnote{cojunto de celdas contiguas de un mismo color} 
de color primario (el cluster que comienza en la esquina superior izquierda). 
Mientras m\'as grande sea el tama\~no de \'este cluster, m\'as cerca se estar\'a de la soluci\'on. 
Es preferible expresarlo con su inverso, es decir, calcular la cantidad de cuadrados del tablero que 
el bloque primario no incluye para que sea decreciente el valor de $h_2(n)$ al acercarse a la soluci\'on. 
Por ejemplo en la Figura \ref{fig1} el valor de esta heur\'istica ser\'ia $h_2(n) = 16$, 
mientras que en la Figura \ref{fig2} ser\'ia $h_2 = 19$. El problema de esta heur\'istica es que no es admisible, 
con lo cual la soluci\'on que encuentra no siempre es la de costo m\'inimo. 
En este problema en particular, dado que el costo es constante e igual a 1 en cada rama, 
no siempre se encuentra la soluci\'on de menor profundidad en el \'arbol. 

\subsection{Cuarta Heur\'istica $H_4$}
Se propuso como cuarta heur\'istica la combinaci\'on de utilizar la $H_1$ con $H_2$, es decir $max\{H_1, H_2\}$. 


\section{Resultados y Conclusiones}

En \'esta secci\'on se muestran los resultados obtenidos a partir de la utilizaci\'on de los distintos algoritmos de
b\'usqueda. A partir de los resultados obtenidos se presentan tambi\'en las conclusiones obtenidas al respecto.

\subsection{Primeras Aproximaciones}

  En la primera prueba que se corri\'o con m\'etodos no informados el resultado obtenido es poco satifactorio, ya que se utiliza fuerza bruta, 
por lo que la memoria que se utiliza es much\'isima (excede los 4GB de RAM que es lo que aproximadamente tienen las PC con las que se realizan las pruebas) 
y el programa no puede finalizar satisfactoriamente su ejecuci\'on en en tableros de $8x8$ en adelante a excepci\'on de profundizaci\'on
iterativa que hasta $8x8$ encuentra la soluci\'on, a expensas de utilizar toda la memoria RAM disponible en el equipo. No obstante, como
DFS no es \'optimo ni completo logra encontrar una soluci\'on en todos los casos, pero a un nivel de profundidad superior.\\
  En cuanto a los m\'etodos informados, las pruebas tuvieron mejores resultados, aunque nuevamente hubo problemas con el uso de memoria
y velocidad de procesamiento para algunas combinaciones de heur\'isticas y dimensiones del tablero.
  Tener en cuenta que para todas las pruebas, se utiliza el estado inicial que se muestra en la Figura \ref{fig4}.

\subsection{BFS}
  La primera prueba que se realiz\'o fue la obtenida utilizando el algoritmo de b\'usqueda no informado BFS para un tablero de $8x8$.
Este algoritmo tiene las caracter\'isticas de que si existe una soluci\'on, encuentra la \'optima, que
en este caso es aquella que posea la menor cantidad cambios de colores realizados. \'Este algoritmo, al ser de fuerza bruta, expande una
enorme cantidad de nodos y el consumo de memoria se vuelve muy grande. 
Debido a esto, no se pudo obtener la soluci\'on al problema con este m\'etodo de b\'usqueda. 
Se utilizaron $4,5GB$ de memoria. En la Tabla \ref{figTable8} se pueden ver los detalles de la corrida.\\

%\textbf{Aclaraci\'on:} El tiempo no es una referencia v\'alida, por el uso de memoria en disco.

  Como se observa, la cantidad de memoria requerida fue considerable. 
La conclusi\'on que se saca de esta prueba es que el consumo de memoria es excesivo, pero al ser un algoritmo de
fuerza bruta no es anormal que esto suceda.

\subsection{DFS}

En la segunda prueba se utiliz\'o el algoritmo de b\'usqueda no informado DFS. Este
algoritmo de b\'usqueda no es ni \'optimo ni completo. En las Tablas \ref{figTable8}, \ref{figTable10} y \ref{figTable14} 
se pueden ver los detalles de la corrida con un tablero de $8x8$, $10x10$ y $14x14$, respectivamente. 

\'Este algor\'itmo, aunque no encuentre la soluci\'on \'optima,
fue el \'unico m\'etodo de b\'usqueda no informado que logr\'o encontrar la soluci\'on en un tablero de dimensiones superiores a $8x8$. 
Para este caso, donde la idea del juego es justamente reducir la cantidad de cambios de colores necesarios para pintar el tablero de un mismo color, 
no ser\'ia muy \'util ya que con el tablero de $8x8$ se resuelve en 24 jugadas, el $10x10$ en 28 y el de $14x14$ en 42, 
lo cual esta fuera de los l\'imites del juego (en el juego original, el m\'aximo de movidas es 30 con un tablero de $14x14$).

Tambi\'en es importante remarcar que la diferencia de tiempo de procesamiento y de nodos expandidos es considerable con los otros m\'etodos de 
b\'usqueda no informados.

\subsection{Profundizaci\'on Iterativa}

El tercer m\'etodo es el algoritmo de b\'usqueda no informado \textbf{Profundizaci\'on iterativa}. 
Este algoritmo de b\'usqueda es \'optimo y completo. 

%\textbf{Aclaraci\'on}: Los nodos frontera corresponden a la \'ultima iteraci\'on del algoritmo. Los nodos explorados fueron 1110105.

Como se puede apreciar en la tabla \ref{figTable8}, al ser el algoritmo de profundizaci\'on iterativa \'optimo y completo, 
se encontr\'o la soluci\'on a un nivel de profundidad $12$, la mitad de la profundidad de la soluci\'on encontrada por \textbf{DFS}. Sin embargo
la soluci\'on se encontr\'o a un costo computacional mucho mayor, como se puede ver en la cantidad de nodos expandidos total 
y en el tiempo de procesamiento es de aproximadamente 2000 veces mayor que el de \textbf{DFS}.

\subsection{Greedy}
El m\'etodo de b\'usqueda \textbf{Greedy} encontr\'o soluci\'on para todos los tableros, 
con todas las heur\'isticas aplicadas. A continuaci\'on se detallan cada una de las corridas. 
Los resultados se pueden ver en las tablas \ref{figTable8}, \ref{figTable10} y \ref{figTable14} respectivamente.

\subsubsection{Greedy - $H_1$}
La utlizaci\'on de esta heur\'istica con Greedy siempre logra encontrar la soluci\'on ya que se realiza
la mayor\'ia del tiempo de la misma forma que una b\'usqueda no informada \textbf{DFS}. 
Esto se debe a que la heur\'istica utilizada devuelve el mismo valor para cada estado hasta niveles de profundidades cercanos a un nodo goal. 
Recien en los \'ultimos niveles de profundidad es que se comienza a ver la diferencia entre estos valores y se aprecia la diferencia 
con el algoritmo no informado.  
%\textbf{VER PORQUE EL TIEMPO DE PROCESAMIENTO ES MENOR Y PORQUE LA CANTIDAD DE NODOS EXPLOTADOS ES MENOR TAMBIEN. NO SE SI TIENE SENTIDO.}

\subsubsection{Greedy - $H_2$}
Esta combinaci\'on de heur\'istica y algoritmo obtuvo muy buenos resultados. 
El nivel de profundidad alcanzado si bien no es el \'optimo, es bastante cercano como se puede ver en los resultados
de las tablas \ref{figTable8} y \ref{figTable10}. L\'ogicamente por como se computa el valor de $h_2(n)$, aumenta el tiempo de procesamiento. 

\subsubsection{Greedy - $H_3$}
Esta heur\'istica, si bien no es admisible, alcanz\'o buenos resultados en cuanto a profundidad alcanzada. En las pruebas realizadas siempre
encuentra la soluci\'on en menor o igual cantidad de jugadas que las otras heur\'isticas. Al mismo tiempo es la que menor tiempo de
procesamiento registr\'o, dado que el c\'alculo que se realiza para obtener el valor $h(n)$ por cada estado es despreciable en comparaci\'on
del resto de las heur\'isticas.

\subsubsection{Greedy - $H_4$}
Al utilizar la combinaci\'on entre $H_1$ y $H_2$, se obtuvieron resultados intermedios entre los resultados logrados individualmente
por la utilizaci\'on de ambas heur\'isticas. Lo \'unico que siempre aumenta es el tiempo de procesamiento, ya que debe computar ambas 
heur\'isticas de cada estado para luego tomar el m\'aximo.


\subsection{A*}
A continuaci\'on se detallan los resultados y conclusiones del m\'etodo de b\'usqueda A* utilizando las diferentes heur\'isticas implementadas.

\subsubsection{A* - $H_1$}
  Con \'esta heur\'istica se encontr\'o la soluci\'on optima con un nivel de profundidad $16$ para un tablero de $10x10$. 
Como se indica anteriormente esta heur\'istica es efectiva cuando el tablero es peque\~no o cuando se est\'a en niveles de profundidades
pr\'oximos a la soluci\'on, caso contrario se comporta como BFS. Como es posible hacer BFS hasta niveles de profundidad 11 con la memoria disponible
en el equipo en el que se realizaron las pruebas, se encuentra la soluci\'on ya que en el nivel 11 comienza a disminur la cantidad de colores
restantes en el tablero con lo cual la heur\'istica deja de comportarse como BFS.\\
  En un tablero mayor a $10x10$ \'esto ya no se cumple y con esta heur\'istica no se puede completar la b\'usqueda por falta de memoria. 
Por otro lado, se puede observar que comparando este m\'etodo con profundizaci\'on iterativa en un tablero de $8x8$ (donde ambos encuentran la soluci\'on), 
\'e ste m\'etodo es ampliamente superior ya que expande una cantidad considerablemente menor de nodos.

\subsubsection{A* - $H_2$}
  Utilizando \'esta heur\'istica se logr\'o encontrar la soluci\'on \'optima en el tablero de $8x8$ con una cantidad de nodos muy inferior 
al m\'etodo BFS. En tableros inferiores a $8x8$, esta heur\'istica resulta menos eficiente que $H_1$ 
ya que una vez que el tablero est\'a en un estado cercano a la soluci\'on, $H_1$ es una mejor estimaci\'on de la distancia real a la soluci\'on 
que $H_2$ y adem\'as $H_1$ requiere menos memoria para computar el valor $h_1(n)$ de cada estado.\\
  En tableros de dimensi\'on superiores, se hubiera esperado que esta heur\'istica sea m\'as eficiente que $H_1$ debido a que es aplicable 
para cualquier profundidad del \'arbol y no solo para los \'ultimos niveles como $H_1$. 
Sin embargo, debido a que $H_2$ tiene un costo computacional y requerimiento de memoria mucho mayor, 
no se logr\'o resolver con esta heur\'istica tableros m\'as grandes por falta de memoria.

\subsubsection{A* - $H_3$}
  Al ser $H_3$ una heur\'istica no admisible, la soluci\'on que encuentra en todos los casos no fue la \'optima. 
Sin embargo, en todos los casos encontr\'o una mejor soluci\'on que Greedy y por ende mejor que DFS. 
Esto se debe a que Greedy y DFS una vez que eligen una rama siempre siguen por ella. En A* al comparar $f(n)$ de todos los nodos frontera 
del \'arbol de b\'usqueda, a pesar de no seguir la soluci\'on \'optima, se eligen mejores ramas que los otros m\'etodos.\\
  Por \'ultimo, considerando que en un tablero de $14x14$ no se logr\'o encontrar la soluci\'on \'optima por falta de memoria 
\'esta combinaci\'on de m\'etodo de b\'usqueda y heur\'istica fue la que consigui\'o la mejor soluci\'on, de 23 jugadas.

\subsubsection{A* - $H_4$}
  La \'ultima heur\'istica probado, al ser una combinaci\'on de dos heur\'isticas admisibles, tambien es admisible y encontr\'o la soluci\'on 
\'optima para tableros de $8x8$ y $10x10$. Ser\'ia esperable que utilizando esta heur\'istica en los primeros niveles de profundidad
predomine $H_2$ y en los \'ultimos $H_1$ por las razones antes mencionadas sobre el comportamiento de $H_1$ en niveles iniciales de profundidad. 
Sin embargo, en tableros chicos como los mencionados, se llega muy r\'apidamente a niveles aproximados a la soluci\'on \'optima y en consecuencia 
predomina $H_1$ y los resultados son similares a utilizar \'unicamente dicha heur\'istica.\\
  En tableros de dimensi\'on superior se deber\'ia haber notado una mejora entre utilizar $H_4$ y utilizar las heur\'isticas de manera 
individual, sin embargo, al igual que pasa con $H_2$, el costo computacional de \'esta heur\'istica impide que obtengamos una soluci\'on
en tableros grandes por falta de memoria.

%% ALAN/MARU: Agregar aca alguna conclusion de porque encontro la solucion comparado a BFS... no concluir que es mejor que BFS
%% porque para eso habria que haber probado con varias  tableros diferentes (iniciales, no en tama;o), y sacar estadisticas...
%% eso lo haremos para la proxima jeje.

\section{Comentarios finales}

  En este trabajo, debido a la representaci\'on de cada estado, hubo limitaciones por la disponibilidad de memoria. 
Al tratar de implementar heur\'isticas que sean m\'as aproximadas al costo real $f(n)^*$, debido a la naturaleza del problema,
se necesitaba mayor poder de procesamiento y memoria para alcanza una soluci\'on \'optima. 
Si bien se realizaron optimizaci\'ones en la implementaci\'on de \'este trabajo, como se vi\'o en los resultados,
algunos m\'etodos de b\'usqueda informados no pudieron llegar a resolver el problema con el tablero del juego original de $14x14$.\\
  Sin embargo, se puede concluir que definitivamente los m\'etodos de b\'usqueda informados, al contar con una buena heur\'istica y sin tener
en cuenta las limitaciones de procesamiento y memoria disponible, expanden una cantidad de nodos considerablemente menor que los no informados.
  Es importante remarcar que a veces la mejor heur\'istica no necesariamente conlleva los mejores resultados, ya que como se vi\'o en \'este trabajo
resultan computacionalmente complejas de procesar y requieren un mayor uso de memoria f\'isica.

\begin{thebibliography}{1}
\bibitem [1]{1} http://www.mindjolt.com/games/fill-zone
\end{thebibliography}

\clearpage

\begin{table}
\centering
\begin{tabular}{l|c|c|c|c|c}
\hline
\hline
\textbf{} & \textbf{Expandidos} & \textbf{Frontera} & \textbf{Prof. alcanzada} & \textbf{Tiempo total} & \textbf{Sol. Encontrada?} \\
\hline
\hline
\textbf{BFS} & 654999 & 936625 & 12 & $769270ms$ & \textbf{No}\\
\textbf{DFS} & 47 & 73 & 24 & $50ms$ & \textbf{Si}\\
\textbf{Prof. Iterativa} & 646530 & 22 & 12 & $105270ms$ & \textbf{Si} \\
\textbf{Greedy con H1} & 35 & 85 & 24 & $19ms$ & \textbf{Si} \\
\textbf{Greedy con H2} & 22 & 55 & 16 & $23ms$ & \textbf{Si} \\
\textbf{Greedy con H3} & 16 & 61 & 16 & $12ms$ & \textbf{Si} \\
\textbf{Greedy con H4} & 32 & 80 & 23 & $30ms$ & \textbf{Si} \\
\textbf{A* con H1} & 3622 & 8467 & 12 & $678ms$ & \textbf{Si} \\
\textbf{A* con H2} & 28392 & 72479 & 12 & $10000ms$ & \textbf{Si} \\
\textbf{A* con H3} & 15 & 60 & 15 & $14s$ & \textbf{Si} \\
\textbf{A* con H4} & 3644 & 8534 & 12 & $907ms$ & \textbf{Si} \\
\end{tabular}
        \caption{Tabla de comparaci\'on para tablero de $8x8$}
        \label{figTable8}
\end{table}

\begin{table}
\centering
\begin{tabular}{l|c|c|c|c|c}
\hline
\hline
\textbf{} & \textbf{Expandidos} & \textbf{Frontera} & \textbf{Prof. alcanzada} & \textbf{Tiempo total} & \textbf{Sol. Encontrada?} \\
\hline
\hline
\textbf{BFS} & - & - & - & - & \textbf{No} \\
\textbf{Prof. Iter.} & - & - & - & - & \textbf{No} \\
\textbf{DFS} & 55 & 85 & 28 & $24ms$ & \textbf{Si} \\
\textbf{Greedy - $H_1$} & 44 & 96 & 28 & $28ms$ & \textbf{Si} \\
\textbf{Greedy - $H_2$} & 24 & 72 & 20 & $29ms$ & \textbf{Si} \\
\textbf{Greedy - $H_3$} & 18 & 65 & 18 & $21ms$ & \textbf{Si} \\
\textbf{Greedy - $H_4$} & 36 & 106 & 28 & $38ms$ & \textbf{Si} \\
\textbf{A* - $H_1$} & 140976 & 319170 & 16 & $129887ms$ & \textbf{Si} \\
\textbf{A* - $H_2$} & 191000 & 488315 & - & $214275ms$ & \textbf{Si} \\
\textbf{A* - $H_3$} & 18 & 72 & 18 & $36ms$ & \textbf{Si} \\
\textbf{A* - $H_4$} & 143182 & 323808 & 16 & $148139ms$ & \textbf{Si} \\
\end{tabular}
        \caption{Tabla de comparaci\'on para tablero de $10x10$}
        \label{figTable10}
\end{table}


\begin{table}
\centering
\begin{tabular}{l|c|c|c|c|c}
\hline
\hline
\textbf{} & \textbf{Expandidos} & \textbf{Frontera} & \textbf{Prof. alcanzada} & \textbf{Tiempo total} & \textbf{Sol. Encontrada?} \\
\hline
\hline
\textbf{BFS} & - & - & - & - & \textbf{No} \\
\textbf{Prof. Iter.} & - & - & - & - & \textbf{No} \\
\textbf{DFS} & 75 & 135 & 42 & $71ms$ & \textbf{Si} \\
\textbf{Greedy - $H_1$} & 67 & 143 & 42 & $59ms$ & \textbf{Si} \\
\textbf{Greedy - $H_2$} & 30 & 90 & 24 & $48ms$ & \textbf{Si} \\
\textbf{Greedy - $H_3$} & 23 & 86 & 23 & $31ms$ & \textbf{Si} \\
\textbf{Greedy - $H_4$} & 54 & 126 & 36 & $83ms$ & \textbf{Si} \\
\textbf{A* - $H_1$} & - & - & - & - & \textbf{No} \\
\textbf{A* - $H_2$} & - & - & - & - & \textbf{No} \\
\textbf{A* - $H_3$} & 23 & 92 & 23 & $44ms$ & \textbf{Si} \\
\textbf{A* - $H_4$} & - & - & - & - & \textbf{No} \\
\end{tabular}
        \caption{Tabla de comparaci\'on para tablero de $14x14$}
        \label{figTable14}
\end{table}


\clearpage
\begin{figure}
        \centering
    \includegraphics[keepaspectratio=true]{images/fig1.png}
        \caption{Fillzone: Tablero 1}
        \label{fig1}
\end{figure}

\begin{figure}
        \centering
    \includegraphics[keepaspectratio=true]{images/fig2.png}
        \caption{Fillzone: Tablero 2}
        \label{fig2}
\end{figure}

\begin{figure}
        \centering
    \includegraphics[keepaspectratio=true]{images//fig3.png}
        \caption{Fillzone: Tablero 3}
        \label{fig3}
\end{figure}

\begin{figure}
        \centering
    \includegraphics[width=6cm]{images//tablero.png}
        \caption{Fillzone: Tablero usado en las pruebas}
        \label{fig4}
\end{figure}


%----------------------------------------------------------------------
% SECTION
%----------------------------------------------------------------------

%\section{Resultados y conclusi\'on}

%Es interesante que observemos como algoritmos como el de L'Ecuyer, que generan n\'umeros pseudo-aleatorion, son de enorme utilidad para una amplia cantidad de estudio de modelos y an\'alisis. En este caso nos resulta clave para abordar el del sistema de propulsión del USS Enterprise.

%\begin{thebibliography}{1}

%\bibitem{lamport}
%Leslie Lamport,
%\newblock {\em A Document Preparation System: {\LaTeX} User's Guide and
%  Reference Manual},
%\newblock Addison-Wesley, Reading, MA, 2nd edition, 1994.
%\newblock Be sure to get the updated version for \latexiie!

%\bibitem{goossens}
%Michel Goossens, Frank Mittelbach, and Alexander Samarin,
%\newblock {\em The {\LaTeX} Companion},
%\newblock Addison-Wesley, Reading, MA, 1994.

%\end{thebibliography}
%\begin{thebibliography}{2}
%\bibitem [1]{1} Apostol T.M., \textit{Volumen 1. Calculus. Segunda Edición}, Reverté, 1982
%\bibitem [2]{2} Mathews J.H., Fink K.D., \textit{Métodos Numéricos con Matlab. Tercera Edición}, Prentice Hall, 2003
%\end{thebibliography}

%----------------------------------------------------------------------

%\begin{biography}{Gregory L. Plett}
%(S'97) was born in Ottawa, ON, in 1968. He received the B.Eng.\ degree
%in computer systems engineering with high distinction from Carleton
%University, Ottawa, in 1990, and the M.S.\ degree in electrical
%engineering from Stanford University, CA, in 1992.  He is currently a
%Ph.D.\ candidate at Stanford University, where he is researching
%aspects of adaptive control under the supervision of Professor Bernard
%Widrow.
%\end{biography}


%\begin{biography}{Istv\'{a}n Koll\'{a}r}
%(M'87--SM'93--F'97) was born in Budapest, Hungary, in 1954. He graduated
%in electrical engineering from the Technical University of Budapest in
%1977 and in 1985 received the degree ``Candidate of Sciences'' (the
%equivalent of Ph.D.) from the Hungarian Academy of Sciences, and the
%degree dr.tech.\ from the Technical University of Budapest.
%\begin{thebibliography}{1}
%\bibitem [1]{1} Hertz J., Krogh A., Palmer R.G., \textit{Introduction to the theory of neural computation, Westview Press,1991}
%\bibitem [2]{2} Prueba Chi2: http://es.wikipedia.org/wiki/Prueba\_\%CF\%87\%C2\%B2
%\bibitem [3]{3} Prueba de Kolmog\'orov-Smirnov: http://es.wikipedia.org/wiki/Prueba\_de\_Kolmog\'orov-Smirnov
%\end{thebibliography}

%From September 1993 to June 1995, he was a Fulbright Scholar and
%visiting associate professor in the Department of Electrical
%Engineering, Stanford University. He is professor of electrical
%engineering, Department of Measurement and Information Systems,
%Technical University of Budapest. His research interests span the
%areas of digital and analog signal processing, measurement theory, and
%system identification. He has published about 50 scientific papers and
%is coauthor of the book \emph{Technology of Electrical Measurements},
%(L.\ Schnell, ed., Wiley, 1993). He authored the \emph{Frequency
%Domain System Identification Toolbox} for Matlab.
%\end{biography}

\end{document}